package DFS_112;

import java.util.ArrayDeque;
import java.util.Queue;

import LCommon.TreeNode;

public class Solution {
	public boolean hasPathSum(TreeNode root, int sum) {
		if (root == null) {
			return false;
		}
		if (root.left == null && root.right == null) {
			return sum == root.val;
		}
		return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);

	}

	public boolean hasPathSum_NR(TreeNode root, int sum) {
		if (root == null) {
			return false;
		}
		Queue<TreeNode> queNodes = new ArrayDeque<TreeNode>();
		Queue<Integer> queVal = new ArrayDeque<Integer>();
		queNodes.offer(root);
		queVal.offer(root.val);
		while (!queNodes.isEmpty()) {
			TreeNode now = queNodes.poll();
			int temp = queVal.poll();
			if (now.left == null && now.right == null) {
				if (temp == sum) {
					return true;
				}
				continue;
			}
			if (now.left != null) {
				queNodes.offer(root.left);
				queVal.offer(root.left.val + temp);
			}
			if (now.right != null) {
				queNodes.offer(root.right);
				queVal.offer(root.right.val + temp);
			}
		}
		return false;
	}

}
